#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        vector<vector<int>> PO(m, vector<int>(n));
        vector<vector<int>> AO(m, vector<int>(n));

        int dx[4] = { 0, 0, 1, -1 };
        int dy[4] = { 1, -1, 0, 0 };
        function<void(vector<vector<int>>&, int, int)>
            dfs = [&](vector<vector<int>>& mp, int r, int c)
            {
                mp[r][c] = 1;
                for (int i = 0; i < 4; i++)
                {
                    int x = r + dx[i];
                    int y = c + dy[i];
                    if (x >= 0 && y >= 0 && x < m && y < n && mp[x][y] == 0 && heights[r][c] <= heights[x][y])
                        dfs(mp, x, y);
                }
            };

        for (int i = 0; i < m; i++)
        {
            if (PO[i][0] == 0) dfs(PO, i, 0);
            if (AO[i][n - 1] == 0) dfs(AO, i, n - 1);
        }
        for (int j = 0; j < n; j++)
        {
            if (PO[0][j] == 0) dfs(PO, 0, j);
            if (AO[m - 1][j] == 0) dfs(AO, m - 1, j);
        }

        vector<vector<int>> ret;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (PO[i][j] && AO[i][j])
                    ret.push_back({ i, j });
        return ret;
    }
};